package org.review.datastructure;

import java.util.Objects;

/**
 * 线索二叉树后，也叫线索链表， 遍历快，不用递归或者栈
 */
public class ThreadBinaryTree {

    private Node1 root;
    private Node1 pre;

    public Node1 getPre() {
        return pre;
    }

    public void setPre(Node1 pre) {
        this.pre = pre;
    }

    public Node1 getRoot() {
        return root;
    }

    public void setRoot(Node1 root) {
        this.root = root;
    }

    public static void main(String[] args) {
        Node1 root = new Node1(1, "根节点");
        Node1 Node2L = new Node1(2, "二级左");
        Node1 Node2R = new Node1(3, "二级右");

        Node1 Node13L = new Node1(4, "3级左");
        Node1 Node13R = new Node1(5, "3级右");

        Node2L.setLeft(Node13L);
        Node2L.setRight(Node13R);

        root.setLeft(Node2L);
        root.setRight(Node2R);

        ThreadBinaryTree tbtree = new ThreadBinaryTree();
        tbtree.setRoot(root);

        tbtree.inOrderThreadTree();
        tbtree.inOrderThreadedTraversal();
    }

    public void inOrderThreadedTraversal() {
        if (root != null) {
            inOrderThreadedTraversal(root);
        }
    }

    private void inOrderThreadedTraversal(Node1 root) {
        Node1 current = root;

        while (current != null) {
//        第一个找到的是节点4
            while (current.getTypeL() == 0) {
                current = current.getLeft();
            }
            // 此时
            System.out.println(current);
            while (current.getTypeR() == 1) {
                current = current.right;
                System.out.println(current);
            }

            current = current.right;
        }
    }

    //    线索化前序
    public void inOrderThreadTree() {
        if (Objects.nonNull(root)) {
            inOrderThreadTree(root);
        } else {
            System.out.println("节点为空！");
        }
    }


    /**
     * 这里的pre 非常重要， 在递归的时候，因为中序，所以它可以是右测树的节点 想不通这个，没法写这个方法
     * 第二点：pre 必须是全局的，因为只有全局，才能达到上述的要求
     *
     * @param node
     */
    public void inOrderThreadTree(Node1 node) {

        if (node == null) {
            return;
        }

        //处理前驱节点
        // 如果左侧不为空，那么就进行递归 如果左侧节点为空，这个时候left需要指向pre
        inOrderThreadTree(node.left);

        if (node.left == null) {
            node.left = pre;
            node.setTypeL(1);
        }

        //处理后继节点
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.setTypeR(1);
        }
//      将当前节点作为  上级节点
        pre = node;

        inOrderThreadTree(node.right);
    }
}

class Node1 {
    private int no;
    private String name;
    private int typeL;
    private int typeR;
    Node1 left;
    Node1 right;

    public int getTypeL() {
        return typeL;
    }

    public void setTypeL(int typeL) {
        this.typeL = typeL;
    }

    public int getTypeR() {
        return typeR;
    }

    public void setTypeR(int typeR) {
        this.typeR = typeR;
    }


    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Node1 getLeft() {
        return left;
    }

    public void setLeft(Node1 left) {
        this.left = left;
    }

    public Node1 getRight() {
        return right;
    }

    public void setRight(Node1 right) {
        this.right = right;
    }

    public Node1(int no, String name) {
        this.no = no;
        this.name = name;
    }



    @Override
    public String toString() {
        return "Node1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", typeL=" + typeL +
                ", typeR=" + typeR +
                '}';
    }
}